1. Field of Invention
The present patent document is directed towards systems and methods for point set matching.
2. Description of the Related Art
Point set matching has been a fundamental problem in many applications. These applications include stereo matching, video stabilization, motion estimation, image registration, object detection, and so forth. Although point set matching is important in many applications, it suffers from some significant issues.
There are at least four significant issues with the point set matching problem. As its name implies, point set matching involves matching query points to database points. Thus, one of the first issues is how to construct matching point pairs.
The second issue involves the problem of outlier points, particularly if there is a high ratio of matching pairs that are actually outliers. Outlier points can have a dramatic negative affect on the resultant transformation obtained from the point set matching process. Robust estimation has been a popular method to deal with outliers, and is reported to be reliable when less than 30% point pairs are outliers. Also, sampling-based methods, such as RANSAC or LMedS, have been used to attempt to handle a large ratio of outliers given sufficient number of sampling.
However, these prior approaches have limitations—especially when dealing with the third issue of point set matching. The third issue involves situations in which query points may have multiple candidate matching points in the database. These prior approaches cannot adequately handle such situations.
Finally, prior approaches to the point set matching problem have been computationally complex. As the number of matched points increased, the computation time and complexity can significantly increase.
Accordingly, systems and methods are needed that can address these issues and produce better results when performing point set matching.